package com.skh.math;

/**
 * 汉明距离
 */
public class HammingDistance {

    /**
     * 两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
     *
     * 给出两个整数 x 和 y，计算它们之间的汉明距离。
     *
     * 注意：
     * 0 ≤ x, y < 231.
     *
     * 示例:
     *
     * 输入: x = 1, y = 4
     *
     * 输出: 2
     *
     * 解释:
     * 1   (0 0 0 1)
     * 4   (0 1 0 0)
     *        ↑   ↑
     *
     * 上面的箭头指出了对应二进制位不同的位置。
     */

    /**
     * 思路:使用自带的API
     * @param x
     * @param y
     * @return
     */
    public int hammingDistance(int x, int y) {
       return Integer.bitCount(x ^ y);
    }

    /**
     * 思路:
     * 为了计算等于 1 的位数，可以将每个位移动到最左侧或最右侧，然后检查该位是否为 1。
     * 这里采用右移位，每个位置都会被移动到最右边。移位后检查最右位的位是否为 1 即可。
     * 检查最右位是否为 1，可以使用取模运算（i % 2）或者 AND 操作（i & 1），这两个操作都会屏蔽最右位以外的其他位。
     *
     * @param x
     * @param y
     * @return
     */
    public int hammingDistance1(int x, int y) {
        int ans = x ^ y;
        int count = 0;
        while (ans != 0) {
            if (ans % 2 == 1) {
                //最右位为1说明符合要求
                count++;
            }
            //向右移1位,继续判断
            ans = ans >> 1;
        }

        return count;
    }
}
